#include <iostream>

using namespace std;

/*
The knapsack problem or rucksack problem is a problem in combinatorial optimization: 
Given a set of items, each with a weight and a value, determine the count of each item
to include in a collection so that the total weight is less than or equal to a given limit
and the total value is as large as possible. It derives its name from the problem faced by 
someone who is constrained by a fixed-size knapsack and must fill it with the most useful items.

Array[i][j] is the max value can be hold in knapsack for i item with capacity j. For each Array[i][j]
we have the recursive formula:
Array[i][j] = MAX (Array[i-1][j], Array[i-1][j-weight[i-1]]+value[i-1];
*/

#define N 8
#define MAX_CAPACITY	200
#define MAX(X,Y)	((X>Y)?X:Y)

int Array[N+1][MAX_CAPACITY+1] = {0};

int KnapSack( int *Weight, int *Value, int ItemNum, int Capacity)
{
	int i,j;

	if( Capacity>MAX_CAPACITY)
		return -1;

	// init Array
	for( i=0; i<=N;i++)
		Array[i][0] = 0;

	for( j=0;j<=Capacity;j++)
		Array[0][j] = 0;		
	
	// Calculate based on formula
	for( i=1; i<=N; i++ )
	{
		for( j=1; j<=Capacity; j++)
		{
			Array[i][j]= Array[i-1][j];
			if( j>=Weight[i-1])
			{
				Array[i][j]= MAX(Array[i][j], Array[i-1][j-Weight[i-1]]+Value[i-1]);
			}
		}
	}

	return Array[N][Capacity];
}

int main()
{
	int weight[N] = {3,9,7,11,4,6,15,10};
	int value[N] =  {7,8,9,10,3,5,12,9};
	int capacity = 25;

	int maxValue = KnapSack( weight, value, N, capacity);
	cout<<"The max value "<<maxValue<<" for capactiy "<<capacity<<endl;

	// Print the Array
	for( int i=0;i<=N;i++)
	{
		for(int j=0;j<=capacity;j++)
			cout<<Array[i][j]<<" ";
		cout<<endl;
	}
	
	cout<<"Press any key to terminate..."<<endl;
	return getchar();
}